#ifndef _Ape__Collections__Map
#define _Ape__Collections__Map

#include <Ape/Object.h>
#include <Ape/Collections/CollectionHelpers.h>
#include <Ape/Exception.h>

namespace Ape {
	namespace Collections {
	
		struct MapNode;
		template <typename K_t, typename V_t>
		class Map;
		
		/**
			Implementation of the map
			@author Roman Gafiyatullin
		*/
		class MapImpl : public Object {
			TYPE_NAME ("Ape::Collections::MapImpl")
		private:
			/**
				the root node of the tree
			*/
			MapNode* m_RootNode;
		protected:
			/**
				ctor
			*/
			MapImpl();
		public:
			/**
				dtor
			*/
			virtual ~MapImpl();
			/**
				Implementation should compare the two keys
				@param k1 - key #1 (left key)
				@param k2 - key #2 (right key)
				@return 1 when k1 > k2, 0 - when k1 = k2, -1 when k1 < k2
			*/
			virtual int CompareKeys (void* k1, void* k2) const = 0;
			virtual void DisposeValues (void* k, void* v) const = 0;
			
		protected:
			void set (void* K, void* V);
			void* get (void* K) const;
			void remove (void* K);
			bool exists (void* K);
			void remove_all();
			void dispose_node (MapNode* node);
		};
		
		template <typename K_t, typename V_t>
		class Map : public MapImpl {
			TYPE_NAME ("Ape::Collections::Map<K_t, V_t>")
		public:
			Map() {}
			virtual ~Map() {
				RemoveAll();
			}
			
			const V_t GetAt (const K_t& k) const {
				void* key = TypedHelper<K_t>::ToHeap (k);
				void* val = get (key);
				TypedHelper<K_t>::Free (key);
				
				V_t ret = TypedHelper<V_t>::ToStack (val);
				//TypedHelper<V_t>::Free(val);
				
				return ret;
			}
			void SetAt (const K_t& k, const V_t& v) {
				void* key = TypedHelper<K_t>::ToHeap (k);
				void* val = TypedHelper<V_t>::ToHeap (v);
				
				set (key, val);
			}
			void RemoveAt (const K_t& k) {
				void* key = TypedHelper<K_t>::ToHeap (k);
				remove (key);
				TypedHelper<K_t>::Free (key);
			}
			
			const V_t operator[] (K_t k) const {
				return getAt (k);
			}
			
			V_t& operator[] (K_t k) {
				if (!KeyExists (k) ) {
					SetAt (k, V_t() );
				}
				void* key = TypedHelper<K_t>::ToHeap (k);
				void* val = get (key);
				TypedHelper<K_t>::Free (key);
				
				V_t& ret = TypedHelper<V_t>::RefToStack (val);
				return ret;
			}
			
			bool KeyExists (const K_t& k) {
				void* key = TypedHelper<K_t>::ToHeap (k);
				bool bExists = exists (key);
				TypedHelper<K_t>::Free (key);
				return bExists;
			}
			
			void RemoveAll() {
				remove_all();
			}
			
			virtual int CompareKeys (void* k1, void* k2) const {
				K_t& r1 = TypedHelper<K_t>::RefToStack (k1);
				K_t& r2 = TypedHelper<K_t>::RefToStack (k2);
				
				if (r1 == r2)
					return 0;
					
				if (r1 > r2)
					return 1;
					
				if (r1 < r2)
					return -1;
					
				throw Ape::Exception (L"The keys cannot be compared correctly (fourth branch: neither eq, nor lt, nor gt)");
			}
			
			virtual void DisposeValues (void* k, void* v) const {
				if (k) {
					TypedHelper<K_t>::Free (k);
				}
				if (v) {
					TypedHelper<V_t>::Free (v);
				}
			}
		};
	}
}

#endif // _Ape__Collections__Map
